#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace Hash
{
	enum  Status
	{
		EXIT,
		DELETE,
		EMPTY
	};

	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s=EMPTY;
	};


	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			int hash=0;
			for (auto ch : key)
			{
				hash *= 31;
				hash += ch;
			}
			return hash;
		}
	};
	template<class K,class V,class Setkey=HashFunc<K>>
	class HashTable
	{
		
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			if (_n * 10 / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K,V> newhash;
				newhash._tables.resize(newSize);
				for (int i = 0; i < _tables.size(); i++)
				{
					if(_tables[i]._s==EXIT)
					newhash.Insert(_tables[i]._kv);
				}
				_tables.swap(newhash._tables);
			}
			Setkey hf;
			size_t hashi = hf(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIT)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIT;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Setkey hf;
			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s==EXIT && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIT)
				{
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else
				{
					printf("[%d]->D\n", i);
				}
			}
			cout << endl;
		}


	private:
		vector<HashData<K, V>> _tables;
		int _n=0;


	};
}